1. Field of the Invention
This invention relates generally to memory management systems and methods. More particularly, this invention relates to memory management circuits and methods for management of nonvolatile memory devices. Even more particularly, this invention relates to page based memory management of nonvolatile memory devices such as Flash Random Access Memory (RAM).
2. Description of Related Art
A solid-state drive (SSD) is a data storage device that uses semiconductor memory devices to store persistent data. An SSD is used to emulate a magnetic or electro-optical hard disk drive. The SSD employs an interface such as the Serial Advanced Technology Attachment (SATA) that allows the SSD to easily replace a hard disk drive in most applications. Other interface formats that may used by the SSD include Parallel Advanced Technology Attachment (PATA), Universal Serial Bus (USB), Peripheral Component Interconnect Express (PCI express), fiber channel (ANSI X3.230-1994, Fiber Channel—Physical and Signaling Interface). SSD systems may use volatile RAM such as static RAM or Dynamic RAM or nonvolatile RAM such as Flash RAM.
Refer now to FIG. 1a for a discussion of a computer system employing an SSD 100 to replace hard disk drive for persistent data. A central processing unit 105 executes a sequence of stored program instructions that are retained in temporary computer memory (RAM) 110 or the persistent memory (SSD) 100. The central processing unit executes four basic functions: a fetch for an instruction and or data from the temporary memory 110 or the persistent memory 100, decode of the instruction data, execution of the instruction, and write back of the result to the temporary memory 110 or the persistent memory 100. The fetch or write back of the resulting data may additionally be a communication with an input/output device 115 such as a printer, display or a network device.
The CPU 105, the temporary memory 110, the persistent memory 100, and the Input/Output device 115 are connected to a system bus 120. The system bus 120 provides the necessary data formatting and conversion for communication between the CPU 105, the temporary memory 110, the persistent memory 100, and the Input/Output device 115. In the example of the persistent memory 100, the system bus provides the communication in a format such as an SATA format or the other formats listed above. The formats such as the SATA format contain the configuration for the logical address within the persistent memory 100, the data, and control information for the fetching and storing of program instructions and data for processing by the CPU 105.
The persistent memory 100 as implemented as an SSD 100 has a controller 125 that decodes the logical address to a physical address and the control information for determining whether the data is to be stored or fetched from the NAND Flash array 130. The NAND Flash array 130 includes nonvolatile memory flash RAM chips that are divided into a number of blocks (for ex. 8192 for a 16 gbit chip). Each block is subdivided into pages (64 pages per block for Single Level memory Cell chips (SLC) or 128 pages for Multi-Level memory Cell chips). The structure of a NAND flash memory chip does not permit reading and writing in a byte per byte basis but can only be accomplished in chunks of one page (typically 4 kb). Additionally, an already written page cannot be overwritten. Writing can only be done to erased pages. The erase unit is a block, 64 or 128 pages. The different unit size for read/write (1 page) and erase (64/128 pages) makes management of flash RAM chips difficult. This also means random write of small chunks of data is quite slow, because blocks must be erased and data of the old block must be copied before writing. A logical-to-physical (LogToPhys) translation table is needed to provide a physical location of data for a given logical address. The logical-to-physical (LogToPhys) translation table is located in the flash memory and must be changed each time the data is to be written.
FIG. 1b illustrates the logical address structure for a flash storage system SSD 100 of the prior art. In this example, a flash RAM nonvolatile memory device 150 is divided into blocks 155 (8192 Blocks). Each block 155 is divided into pages 160 (64 pages) and each page 160 is divided into sectors 165 (8 sectors). Each of the sectors 165 is divided into bytes 170 (generally 512 bytes). The sector is normally defined as the smallest unit to be covered by ECC and any required overhead bits 167. As technology is advancing the sector and the page may actually become equal at 4K Bytes (512 Bytes×8 sectors).
Consumer oriented flash storage cards are very price sensitive. Controllers for flash storage cards are generally single chip items with a minimal number of external components and no external RAM memory. If the controller of a flash storage card has internal amount of RAM memory, it is very limited. In order to conserve RAM space, it is state of the art for these controllers to use a block oriented management process. This means an entry within the logical-to-physical (LogToPhys) translation table is a block number. A block address covers a large amount of data, typically 256 Kb or 512 Kb, this table changes slowly while writing sequentially.
FIG. 1c illustrates an exemplary flash storage system SSD 100 of the prior art. An address signal 200 is applied to a physical address decode circuit 205. The physical address is structured to have lower order bits (0 . . . 2) are designated as pointing to sectors 201 within a page. The next higher order bits (3 . . . 8) are designated as pointing to the pages 202 within a block. The next higher order bits (9 . . . 21) are designated as pointing to the block 203. The highest order bit (22) is designated as pointing to the chip location 204.
In this example the array of Flash RAM nonvolatile memory devices 235 consists of at least two Flash RAM nonvolatile memory chips 240 and 245. The physical address decode circuit 205 generates a physical address 250 that identifies the blocks 242 and 247 within the two Flash RAM nonvolatile memory chips 240 and 245 that are to be access for reading or writing of data 220.
A control signal 210 provides the encoded control word that is sent to the control logic 215 to develop the control signals 270 for the array of Flash RAM nonvolatile memory devices 235 for reading or writing of data to the two Flash RAM nonvolatile memory chips 240 and 245. Input Data signals 220 provide the new sector data 222 that is to be read from or written to the array of Flash RAM nonvolatile memory devices 235. The Data signals 220 are retained by the page buffer 225 until they are to be read to external host circuitry or written to the array of Flash RAM nonvolatile memory devices 235. The data is transmitted on a data bus 260 between the page buffer and the array of Flash RAM nonvolatile memory devices 235.
As is known in the art, the SATA interface provides addressing for reading or writing sectors of a magnetic or electro-optical hard drive. To be compatible with the magnetic or electro-optical hard drive operation, an SSD must also operate at a sector level to communicate with an SATA interface. The example, as shown in FIG. 1c, illustrates an update of a single sector having a logical block address (LBA) 51200. The low order bits (0 . . . 8) for the sector 201 and the page 202 are the same for the logical and physical address and represent the sector position within a block 203. The high order bits (9 . . . 22) 203 and 204 of the logical address are an index into a logical-to-physical table 230. The logical-to-physical table 230 has as many entries 232 as there are blocks. In each entry 232, the highest order bit indicates, physically, which of the two Flash RAM nonvolatile memory chips 240 and 245 are to be accessed for reading, writing, or erasing. The low order bits of the entry 232 indicate the physical block number within one of the two Flash RAM nonvolatile memory chips 240 and 245. In this example, the data that is resident block 100 242 in the Flash RAM nonvolatile memory chip (0) 240 is replaced with the erased block 200 247 of the Flash RAM nonvolatile memory chip (1) 245. The block 200 247 is to receive the new sector data 222 from the external circuits. All other sectors of the block 100 242 are copied from the old block 100 242. This copy operation is referred to as block recombination.
To accomplish this update, the address 200 is decoded by the physical address decoder 205 and the high order bits (9 . . . 22) are used to point to the index address to the logical-to-physical table 230. The physical address for the block 100 242 is transmitted to the array of Flash RAM nonvolatile memory devices 235. At this same time the control logic 215 receives and decodes the control information and commands the physical address decoder 205 to transmit the address. Simultaneously, the control logic 215 sends the array control signals 270 to the array of Flash RAM nonvolatile memory devices 235. The Flash RAM nonvolatile memory chip 240 is instructed to read the data of the entire block 100 242 to the page buffer 225 on the data bus 260. The control logic 215 instructs the page buffer 225 to merge the new data 220 with the data read from the block 100 242 in the location of the sector 4296704 247. The control logic then determines that the data from block 100 242 is to written back to the block 200 247 of the Flash RAM nonvolatile memory chip (1) 245 and instructs the physical address decoder 205 to update the contents of the index of the logical-to-physical table 230 from the physical block 100 to the physical block 8392 (8192+200). The block buffer 225 is instructed to write the updated block to the block 200 247 with the new data in the sector 51200. The control logic then instructs the Flash RAM nonvolatile memory chip (0) 240 to erase the block 100.
The block based management, as described, is very fast for sequential operation, when whole blocks are completely overwritten with new data. However the process slows down for random write depending on the amount of block recombination overhead. Modern high capacity solid state drives (SSD) must compete with much cheaper mechanical hard disc drives (HDD). To be competitive, SSDs must be much faster than HDDs especially the random write speed. Therefore high speed is a much more important issue than controller price and these kinds of controllers usually have a big external DRAM to bring up speed considerably. What is needed to benefit from this new hardware architecture are a better internal methods and circuits for management of the array of Flash RAM nonvolatile memory devices 235.
“A Space-Efficient Flash Translation Layer for Compact Flash Systems”, Kim, et al., IEEE Transactions on Consumer Electronics, May 2002, Vol.: 48, Issue: 2, pp: 366-375 describes an intermediate software layer called a flash translation layer (FTL) that is employed to redirect logical addresses from the host system to physical addresses in flash memory. A flash translation layer combines a page write and block erase granularities in address translation. A coarse grain address translation lowers the resources required to maintain translation information, and a fine grain address translation is efficient in handling small size writes.
U.S. Pat. No. 5,404,485 (Ban) provides a flash memory, virtual mapping system that allows data to be continuously written to unwritten physical address locations. The virtual memory map relates flash memory physical location addresses in order to track the location of data in the memory.
U.S. Pat. No. 5,963,983 (Sakakura, et al.) teaches a memory device having a work memory for storing logical address-physical address conversion information. The semiconductor memory device is addressed as predetermined sector units. The memory device has a data storage having a nonvolatile memory that can be electrically rewritten. An interface connected to the host computer system receives an access request. The volatile work memory stores a table of the page addresses of the nonvolatile memory for converting the requested logical sector address into a physical sector address among a physical memory space of the nonvolatile memory. A second table in the volatile work memory stores the addresses of blocks of pages, for converting a logical page numbers addressed by the access request the page numbers of the block in the nonvolatile memory. A second access control means refers to the second table retrieve logical sector address to acquire a corresponding physical page numbers for the block.
U.S. Pat. No. 6,591,328 (Iida, et al.) describes a non-volatile memory with a storing address control table data formed of logical addresses and physical addresses. The logical/physical address control table controls the location of data recorded discretely in the non-volatile memory. The logical/physical address control table is composed of a plurality of blocks each serving as a data deletion unit and including adjacent pages which each have a fixed length and serve as a data read/write unit. An operand data block includes operand identification data that indicates data stored in the operand data block is, in fact, operand data. The logical/physical control table block located in the non-volatile memory includes control-table identification data that indicates that data that is stored in the control table data that includes logical addresses and physical addresses.
U.S. Pat. No. 6,598,115 (Kaki, et al.) teaches a semiconductor storage apparatus that includes multiple nonvolatile flash memories and utilizing logical to physical sector conversion. A controller converts logical sector numbers for blocks of data into physical sector numbers of areas of nonvolatile flash semiconductor memories where the blocks of data are to be written.
U.S. Pat. No. 7,386,655 (Gorobets, et al.) provides a method with indexing for a scratch pad and update blocks in non-volatile memory. Update data is recorded selectively in at least two interleaving streams such as either into an update block or a scratch pad block depending on a predetermined condition. The scratch pad block is used to buffered update data that is ultimately destined for the update block in the nonvolatile.
U.S. Pat. No. 7,386,700 (Lasser) describes flash memory management system for a memory for accessing data from a host. The system includes physical units and virtual units of the memory and a mapping mechanism of each virtual unit into one or more physical units.
U.S. Patent Application 2006/0069852 (Aasheim, et al.) provides a free sector manager for data stored in flash memory devices. A flash driver tracks data stored in a flash memory device through the use of logical-to-physical sector mapping. The mapping is stored in a data structure and allows data to be written into the next free physical sector in the flash memory medium. Write operations complete quickly, because there is no need to perform an erase operation in order to write new data on to the flash memory medium. The logical-to-physical sector mapping stored in data structure is backed-up on the flash memory medium. In the event there is a catastrophic power interruption, logical-to-physical sector mapping can easily be reestablished by scanning the backed-up mapping in the flash memory medium.